package club.xiaojiawei.back;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/21/22 8:48 PM
 * @question 491. 递增子序列
 * @description 给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
 * 数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
 */
public class FindSubsequences491 {

    public static void main(String[] args) {
        FindSubsequences491 test = new FindSubsequences491();
        System.out.println(test.findSubsequences2(new int[]{1, 2, 3, 4}));
    }

    /**
     * 递归回溯+HashSet去重
     * @param nums
     * @return
     */
    public List<List<Integer>> findSubsequences(int[] nums) {
        this.length = nums.length;
        recursion(nums, 0);
        return new ArrayList<>(this.result);
    }

    Set<List<Integer>> result = new HashSet<>();

    List<Integer> temp = new ArrayList<>();

    int length = 0;

    public void  recursion(int[] nums, int startIndex){
        if (startIndex == this.length){
            return;
        }
        for (int i = startIndex; i < length; i++){
            if (i != startIndex && nums[i] == nums[i - 1]){
                continue;
            }
            if (temp.size() == 0){
                temp.add(nums[i]);
            }else if (temp.get(temp.size() - 1) <= nums[i]){
                temp.add(nums[i]);
            }else {
                recursion(nums, i + 1);
                continue;
            }
            if (temp.size() > 1){
                result.add(new ArrayList<>(temp));
            }
            recursion(nums, i + 1);
            temp.remove(temp.size() - 1);
        }
    }

    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    /**
     * 官方-递归枚举 + 减枝
     * 用二进制法的思路来看待这个递归方法
     * @param nums
     * @return
     */
    public List<List<Integer>> findSubsequences2(int[] nums) {
        dfs(0, Integer.MIN_VALUE, nums);
        return ans;
    }

    public void dfs(int cur, int last, int[] nums) {
        if (cur == nums.length) {
            if (temp.size() >= 2) {
                ans.add(new ArrayList<Integer>(temp));
            }
            return;
        }
        if (nums[cur] >= last) {
//        带上当前元素进行下一个递归，相当于二进制法里的1,被选中
            temp.add(nums[cur]);
            dfs(cur + 1, nums[cur], nums);
            temp.remove(temp.size() - 1);
        }
//        当当前元素和上一个元素不一样时才进行下一次递归，因为上一个元素已经和后面的元素递归过了，如果再递归就重复了
        if (nums[cur] != last) {
//            不带当前元素进行下一次递归，相当于二进制法里的0,未被选中
            dfs(cur + 1, last, nums);
        }
//        两个dfs是递归持续推进穷举的关键
    }

}
